package main.Q1501_1600;

public class Q1571_1580 {
    public static void main(String[] args) {
        System.out.println("Question1571：");
        System.out.println("Question1572：矩阵对角线元素的和");
        System.out.println("Question1573：");
        System.out.println("Question1574：删除最短的子数组使剩余数组有序");
        int[] arr={1,2,3,10,0,7,8,9};
        System.out.println(new Question1574().findLengthOfShortestSubarray(arr));
        System.out.println("Question1575：");
        System.out.println("Question1576：");
        System.out.println("Question1577：");
        System.out.println("Question1578：");
        System.out.println("Question1579：");
        System.out.println("Question1580：");
    }
}

class Question1572{
    public int diagonalSum(int[][] mat) {
        int length=mat.length,total=0;
        for (int i=0;i<length;i++){
            total+=mat[i][i];
            total+=mat[i][length-1-i];
        }
        if (length%2!=0){//奇数行，
            total-=mat[length/2][length/2];
        }
        return total;
    }
}

class Question1574{
    public boolean process(int[] arr,int midStart,int midEnd,int remove){
        int length=arr.length;
        for (int i=midEnd-remove,j=midEnd+1;i<midStart;i++,j++){
            if (arr[i]<=arr[j]) return true;
        }
        return false;
    }
    public int findLengthOfShortestSubarray(int[] arr) {
        int leftInc=0,rightInc=arr.length-1,result=0;
        for (int i=0;i<arr.length;i++){//左侧递增区间
            if (arr[i]>=arr[leftInc]) leftInc=i;
            else break;
        }
        if (leftInc==arr.length-1) return 0;
        for (int i=arr.length-1;i>=0;i--){//右侧递增区间
            if (arr[i]<=arr[rightInc]) rightInc=i;
            else break;
        }
        result=rightInc-leftInc-1;
        int high=Math.min(rightInc,arr.length-leftInc-1);
        while (result<high){
            int temp=result+(high-result)/2;
            if (process(arr,leftInc+1,rightInc-1,temp)) high=temp;
            else result=temp+1;
        }
        return result;
    }
}